home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1994 / MacHack 1994.toast / MacHack™ 1987-1994 / MacHack™ '91 / '91 Attendee Contributions / Rotate Src / Notes < prev    next >
Encoding:
Text File  |  1989-03-15  |  3.4 KB  |  87 lines  |  [TEXT/MPS ]
  1. MacTutor Article Notes:
  2.  
  3. Previous articles
  4.     Eor & copyBits
  5.         Mathematically elegant algorithm
  6.         Computationally inefficient
  7.     Assembler routine
  8.         More direct rotation
  9.     Optimization
  10.         peephole methods
  11.         no consideration for algorithm
  12.     This article
  13.         Complete set of rotations
  14.         new algorithms
  15.         optimized techniques
  16.         no claim to be the end
  17.  
  18. Why talk about rotation
  19.     Mac is graphic, so we may do them frequently in graphic applications
  20.     awkward problem, but easy to relate to
  21.         must take individual bits from a column in the source bitmap
  22.              to generate bytes and words for destination bitmap
  23.         this requires lots of bit orientated operations
  24.         Efficient strategies can cause large changes in the relative
  25.             cost to perform these operations, as prev articles show
  26.     Allows us to demonstrate technique
  27.  
  28. This article's focus
  29.     Using Macros to develop efficient set of similar routines
  30.     Some more coding tips
  31.     
  32. Bitmaps and their rotations
  33.     Complete set of rotations
  34.         rotate left or right 90°
  35.         mirror horizontal or vertical
  36.         rotate 180°
  37.         flip across the diagonals topLeft to lowRight, FL 
  38.             lowLeft to topRight: FR
  39.         final state, no rotation at all.
  40.     Rotation state
  41.         Application may take user input as an object
  42.         Apply multiple rotations
  43.         User loses track of original orientation
  44.         rotation state tells where object is, after repeated rotation xforms
  45.  
  46.     Simpler to explain just one casein single article,
  47.         but let's get ambitious.
  48.     Goal to create routines with common manipulation Macros,
  49.         so that as we develop them, optimizations and bug fixes in one rotation routine
  50.         are applied consistantly to other symetrically related operations
  51.     Macros allow us to have optimally unwound code emitted for each routine,
  52.         with the structural symmetries inherent in them preserved at the source 
  53.         code level, hopfully assuring a more structured and correct implementation
  54.  
  55.     Bitmap is defined within any Rect to the exact bit
  56.         image in the map is always aligned to the anchor point at the top left
  57.         bitmap rows are rounded up to ta whole word boundary
  58.             for more efficient bitmap manipulation
  59.         These extra slop bits, when rotated, can complicate the rotation algorithms
  60.     Efficient to pick a block of bits in registers
  61.         carve off column bits to build a row byte or word
  62.         we have 8 32 bit data registers, D0-D8 to do bit manuplications with
  63.         they can hold a total of 16 words in their high and low ends
  64.     It would be nice if we can work on blocks of 16 words at a time
  65.         we can't require bitmaps to have rows and columns on 16 bit boundaries
  66.         so, we must contend with slop bits on the right and the bottom of the Rect
  67.         
  68.     Some pictures can show how these extra bits are rotated 
  69.         by the 8 possible rotation transformation states
  70.             { rotation pictures }
  71.     The processing iterations
  72.         start in top left
  73.         get a block (for rotation)
  74.         process words down the block
  75.             carving off bits from the left to build output word
  76.             bits forward or reversed
  77.         go to next block of the same rows
  78.         at end of row, drop to next set of rows, and process again, left to right
  79.         finished at end of column
  80.     slop bit handling
  81.         slop bits are left on the right, left top and bottom of the resultant Rect
  82.         slop bits on the bottom are delt with by not storing words beyond the end
  83.         Slop bits in the bitmap on the right are easy, 
  84.             the destination bitmap requires them
  85.         Slop bits in the bitmap on the left are handled after the bitmap has been generated
  86.             by shifting the resultant bitmap left by the number of slop bits
  87.